//
// Description: 918. 环形子数组的最大和
// Created by Loading on 2022/6/18.
//

#include <bits/stdc++.h>

using namespace std;

int maxSubarraySumCircular(vector<int> &nums) {
    /*
     * 1、若最大子数组未环绕，则直接求解
     * 2、若最大子数组环绕，则最小子数组一定不环绕，用数组总和 - 最小子数组和即可
     *
     * 证明：假设最大子数组的区间为[l1,r1]，最小子数组的区间为[l2,r2]，
     *      如果两个区间内存在元素，例如：[l1,r1],v1,v2,v3,[l2,r2],v4……
     *      若v1 + v2 + v3 >= 0，则其一定可以并入最大子数组和中；
     *      若v1 + v2 + v3 < 0，则其一定可以并入最小子数组和中；v4同理。
     *
     *      故，环形数组的最大子数组和最小子数组一定没有交集，且并集为全集。
     */
    // 数组总和
    int sum = 0;
    // 最大子数组和，最小子数组和（若元素全为正数，则为0）
    int max_sub = nums[0], min_sub = nums[0];
    // 当前位置最大子数组和，当前位置最小子数组和（若元素全为正数，则为0）
    int max_curr = 0, min_curr = 0;

    for (auto &x : nums) {
        max_curr = max(max_curr + x, x);
        min_curr = min(min_curr + x, x);
        max_sub = max(max_sub, max_curr);
        min_sub = min(min_sub, min_curr);
        sum += x;
    }

    // 若最大子数组和为负，则全部元素为负，直接返回最大子数组和，否则与数组总和 - 最小子数组和取较大值
    return max_sub > 0 ? max(max_sub, sum - min_sub) : max_sub;
}

int main() {
    vector<int> nums{5, -3, 5};

    auto res = maxSubarraySumCircular(nums);

    cout << res << endl;

    return 0;
}